package sort;

/**
 * 堆排序
 */
public class HeapSort {

    //最大优先队列 变换元素值
    public static void main(String args[]) {
        System.out.println("输入：");
        int nums[]=new int[]{2,7,1,3,6,9,1,5,8,4};
        printIntArray(nums);
        System.out.println("\n建堆：\n");
        buildHeap(nums,true);
        printIntArray(nums);
        increaseQueue(nums,9,9);
        System.out.println("输出：");
        printIntArray(nums);

    }

    /**
     * 优先队列下标某个元素值变为value（value必须大于原先值）
     * （其他插入和删除）均可通过此方法间接获取到
     * @param nums
     * @param index
     * @param value
     */
    public static void increaseQueue(int nums[],int index,int value){
        int indexValue=nums[arrayIndex(index)];
        if(indexValue>value)
        {
            return ;
        }
        int parentIndex=index/2;
        int currentIndex=index;
        while(parentIndex >0 && value>nums[arrayIndex(parentIndex)])
        {
            nums[arrayIndex(currentIndex)]=nums[arrayIndex(parentIndex)];
            currentIndex=parentIndex;
            parentIndex=parentIndex/2;
        }
        nums[arrayIndex(currentIndex)]=value;
    }



    //堆排序
    public static void main_1(String args[]){

        System.out.println("输入：");
        int nums[]=new int[]{2,7,1,3,6,9,1,5,8,4};
        printIntArray(nums);
        //true:生成最大堆 从小到大排序
        //false:生成最小堆 从大到小排序
        maxHeapSort(nums,true);
        System.out.println("\n输出：\n");
        printIntArray(nums);

    }

    /**
     * 堆排序
     * @param nums
     */
    public static void maxHeapSort(int[] nums,Boolean maxStatus){
        //建堆
        buildHeap(nums,maxStatus);
        int heapSize=nums.length;
        int temp;
        while(heapSize>1){
            //交换
            temp =nums[0];
            nums[0]=nums[arrayIndex(heapSize)];
            nums[arrayIndex(heapSize)]=temp;
            heapSize=heapSize-1;
            //重新保持堆属性
            keepHeapProperty(nums,1,heapSize,maxStatus);
        }
    }
    public static void  buildHeap(int[] nums,Boolean maxStatus){
        //nums.length/2内部叶子节点的末节点
        for(int i=nums.length/2;i>0;i--){
            keepHeapProperty(nums,i,nums.length,maxStatus);
        }
    }
    /**
     * 保持堆的性质
     * @param nums
     * @param i
     * @param heapSize
     * @param maxStatus true：最大堆 false 最小堆
     */
    public static void keepHeapProperty(int nums[],int i,int heapSize,boolean maxStatus){

        int left=2*i;//左子树
        int right=2*i+1; //右子树
        int maxIndex=i;
        //从三个节点中 算出 最大/最小节点
        if(maxStatus){
            if(left<=heapSize && nums[arrayIndex(i)]<=nums[arrayIndex(left)]){
                maxIndex=left;
            }
            if(right<=heapSize && nums[arrayIndex(maxIndex)]<=nums[arrayIndex(right)]){
                maxIndex=right;
            }
        }
        else{
            if(left<=heapSize && nums[arrayIndex(i)]>=nums[arrayIndex(left)]){
                maxIndex=left;
            }
            if(right<=heapSize && nums[arrayIndex(maxIndex)]>=nums[arrayIndex(right)]){
                maxIndex=right;
            }
        }

        if(maxIndex!=i){
            //交换
            int temp=nums[arrayIndex(i)];
            nums[arrayIndex(i)]=nums[arrayIndex(maxIndex)];
            nums[arrayIndex(maxIndex)]=temp;
            keepHeapProperty(nums,maxIndex,heapSize,true);
        }

    }

    //计算java数组的下标
    public static int arrayIndex(int i){
        return --i;
    }
    //打印
    public static void printIntArray(int a[]){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+"--");
        }
    }
}
